'''
https://leetcode.cn/problems/add-bold-tag-in-string
'''
from typing import List


class Node:
    def __init__(self):
        self.end = False
        self.next = {}


class Solution:

    def add(self, word):
        cur = self.root
        for char in word:
            if char not in cur.next:
                cur.next[char] = Node()
            cur = cur.next[char]
        cur.end = True

    def addBoldTag(self, s: str, words: List[str]) -> str:
        self.root = Node()
        for word in words:
            self.add(word)
        n = len(s)
        intervals = []
        for i in range(n):
            cur = self.root
            for j in range(i, n):
                if s[j] not in cur.next:
                    break
                cur = cur.next[s[j]]
                if cur.end:
                    intervals.append([i, j])
        if not intervals:
            return s
        # 合并区间
        final_interval = [intervals[0]]
        for start, end in intervals[1:]:
            if start - 1 <= final_interval[-1][1]:
                final_interval[-1][1] = max(end, final_interval[-1][1])
            else:
                final_interval.append([start, end])

        res = ''
        last_end = 0
        for start, end in final_interval:
            res += s[last_end:start]
            res += f'<b>{s[start: end + 1]}</b>'
            last_end = end + 1
        res += s[last_end:n]
        return res


# s = "abcxyz123"
# s = "1abcxyz1234"
# words = ["abc", "123"]
# s = "aaabbb"
# words = ["aa", "b"]
s = "aaabbcc"
words = ["aaa", "aab", 'bc', 'aaabbcc']
print(Solution().addBoldTag(s, words))
